This section introduces aspects that may help facilitate a better understanding of the inventions. Accordingly, the statements of this section are to be read in this light and are not to be understood as admissions about what is prior art or what is not prior art.
A compressive sensing scheme allows compression of a sparse vector x of real or complex numbers (that is, a vector whose entries are primarily zeros, only few being non-zero) into a short vector y. The vector x can then be reconstructed from y with high accuracy. Such compressive sensing schemes have numerous applications.
Typically the number of entries of y (say M) is much smaller than the number of entries of x (say N). The number N/M is the compression ratio. Thus, instead of keeping in memory (or instead of transmitting, working with, etc.) N real (complex) numbers we have to keep only M real (complex) numbers.
Below is a list of references that are referred to throughout the present specification:
[1] A. R. Calderbank, S. Howard, S. Jafarpour, “Sparse reconstruction via the Reed-Muller Sieve,” IEEE International Symposium on Information Theory, pp. 1973-1977, 2010.
[2] A. R. Calderbank, S. Howard, S. Jafarpour, “Construction of a Large Class of Deterministic Sensing Matrices That Satisfy a Statistical Isometry Property,” IEEE Journal of Selected Topics in Signal Processing, pp. 358-374, Vol. 4., no. 2, 2010.
[3] A. R. Calderbank, E. Rains, P. W. Shor, N. J. A. Sloane, “Quantum Error Correction Via Codes Over GF(4),” IEEE Trans. on Information Theory, vol. 44, pp. 1369-1387, 1998.
The compressive sensing scheme proposed in [1,2] has good performance. In particular, it has a good compression ratio N/M, it affords a low-complexity decompression algorithm (i.e., reconstruction of x from y), and it has a good accuracy of decompression. However, it does have a high compression complexity, that is, the complexity of computing y from x.
Thus, new techniques that are able to reduce compression complexity would meet a need and advance compression technology in general.
Specific embodiments of the present invention are disclosed below with reference to FIGS. 1-3. Both the description and the illustrations have been drafted with the intent to enhance understanding. For example, the dimensions of some of the figure elements may be exaggerated relative to other elements, and well-known elements that are beneficial or even necessary to a commercially successful implementation may not be depicted so that a less obstructed and a more clear presentation of embodiments may be achieved. In addition, although the logic flow diagrams above are described and shown with reference to specific steps performed in a specific order, some of these steps may be omitted or some of these steps may be combined, sub-divided, or reordered without departing from the scope of the claims. Thus, unless specifically indicated, the order and grouping of steps is not a limitation of other embodiments that may lie within the scope of the claims.
Simplicity and clarity in both illustration and description are sought to effectively enable a person of skill in the art to make, use, and best practice the present invention in view of what is already known in the art. One of skill in the art will appreciate that various modifications and changes may be made to the specific embodiments described below without departing from the spirit and scope of the present invention. Thus, the specification and drawings are to be regarded as illustrative and exemplary rather than restrictive or all-encompassing, and all such modifications to the specific embodiments described below are intended to be included within the scope of the present invention.